package com.nowcoder.arithmetic;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 打印二叉树的层序遍历
 * User: Ruijie Date: 2016/8/31
 */
public class BinaryTreeLevelOrderTraversal {

    public static class TreeNode {

        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public static ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
        Queue<TreeNode> q=new LinkedList<TreeNode>();
        if(root!=null){
            q.offer(root);
            while(!q.isEmpty()){
                int size=q.size();
                ArrayList<Integer> list=new ArrayList<Integer>();
                while(size>0){
                    TreeNode node=q.peek();
                    list.add(node.val);
                    q.poll();
                    if(node.left!=null){
                        q.offer(node.left);
                    }
                    if(node.right!=null){
                        q.offer(node.right);
                    }
                    size--;
                }
                result.add(list);
            }
        }
        return result;
    }
    public static ArrayList<ArrayList<Integer>> levelOrder1(TreeNode root){
        ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
        int level=0;
        if(root!=null){
            level=getTreeLevel(root);
        }
        for(int i=1;i<=level;i++){
            ArrayList<Integer> list=new ArrayList<Integer>();
            getLevalData(root,i,list);
            result.add(list);
        }
        return result;
    }
    public static boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetric(root.left,root.right);
    }

    private static boolean isSymmetric(TreeNode left, TreeNode right) {
        if(left==null&&right==null){
            return true;
        }
        if(left!=null&&right!=null){
            if(left.val==right.val){
                return isSymmetric(left.left,right.right)&&isSymmetric(left.right,right.left);
            }
        }else{
            return false;
        }
        return false;
    }

    /**
     * 获取每层数据
     * @param root
     * @param level
     * @param list
     */
    private static void getLevalData(TreeNode root, int level, ArrayList<Integer> list) {
        if(root==null){
            return;
        }
        if(level==1){
            list.add(root.val);
        }else{
            getLevalData(root.left,level-1,list);
            getLevalData(root.right,level-1,list);
        }

    }

    private static int getTreeLevel(TreeNode root) {
        if(root==null){
            return 0;
        }
        return Math.max(getTreeLevel(root.left),getTreeLevel(root.right))+1;
    }

    public static void main(String[] args) {
        TreeNode root=new TreeNode(3);
        root.left=new TreeNode(9);
        root.right=new TreeNode(20);
        root.right.left=new TreeNode(15);
        root.right.right=new TreeNode(7);
        System.out.println(levelOrder(root));
        System.out.println(levelOrder1(root));
        TreeNode head=new TreeNode(1);
        head.left=new TreeNode(2);
        head.right=new TreeNode(2);
        head.left.left=new TreeNode(3);
        head.left.left.left=new TreeNode(4);
        head.right.right=new TreeNode(3);
        head.right.right.right=new TreeNode(4);
        TreeNode head1=new TreeNode(1);
        TreeNode head2=new TreeNode(1);
        head2.left=new TreeNode(2);
        System.out.println(isSymmetric(head));
        System.out.println(isSymmetric(head1));
        System.out.println(isSymmetric(head2));

        TreeNode h=new TreeNode(2);
        h.left=new TreeNode(3);
        h.right=new TreeNode(3);
        h.left.left=new TreeNode(4);
        h.left.right=new TreeNode(5);
        h.right.left=new TreeNode(5);
        h.right.right=new TreeNode(4);
        System.out.println(isSymmetric(h));
    }

}
